The present invention relates to a technique for transferring or swapping data stored in data blocks in randomly accessible storage devices such as magnetic disk drives, magnetic optical disk drives, PC card semiconductor memories and CF card semiconductor memories. More specifically, the invention relates to a technique for performing fragmentation with a decreased burden on the host apparatus at higher speed.
The magnetic disk drive is a random access storage device capable of accessing random storage locations on its magnetic disk or a recording medium. In addition, the drive is a block device performing data input and output in data blocks each having a plurality of bytes. A magnetic disk is divided into a plurality of data blocks of a fixed size formed along circular tracks. The data block is the smallest unit when the host apparatus reads/writes data from/to the magnetic disk drive and usually called the sector. Meanwhile, the cluster is defined as a set of plural sectors and the smallest unit for the host apparatus to manage the storage locations of files on the magnetic disk. Accordingly, any small file uses at least one cluster when the file is recorded on the magnetic disk.
File management of a magnetic disk drive by the host apparatus is done by the operating system (OS). The OS has a file management system which is a mechanism to manage files in a block device through a table to associate files with storage locations. The file management system depends on the OS. Among those available, the FAT file system and the NTFS are for Windows (trademark of Microsoft Co., Ltd.) and the HFS is for MAC (trademark of Apple Computer, Inc.)
The magnetic disk drive typically has a plurality of recording surfaces. Further, each recording surface has a plurality of tracks and each track has a plurality of sectors. When a head accesses a desired sector, CHS parameters (cylinder number/head number/sector number) corresponding to that sector are specified in the magnetic disk drive. On the other hand, it has become common that to manage data storage locations, the host apparatus uses a single parameter called the logical block address (hereinafter denoted as LBA) instead of CHS parameters. For a head to access a desired sector in this case, the magnetic disk drive internally translates the LBA to CHS parameters. Serial LBAs are sequentially allocated to sectors on a one-to-one basis.
Sequential allocation of serial LBAs to a magnetic disk results in serial sectors along each track on either recording surface. A file is a unit of collective information for recording data and programs on a magnetic disk. Contiguous recording of the information constituting a file in serial sectors is favorable to the computer when it accesses the magnetic disk in order to read data or a program into the memory since the magnetic disk drive can reduce the seek time and rotary latency.
However, although at the beginning, a plurality of files can be recorded sequentially and contiguously in sectors or clusters on the magnetic disk, unallocated clusters will occur between consecutive allocated clusters as some files are deleted and individual files are partly deleted. When a new file is recorded, the information constituting the file will be scattered to separate storage locations since the OS tries to use unallocated clusters between allocated clusters in order to make the effective use of the recording space. Fragmentation refers to a condition of the disk in which files recorded thereon are divided into pieces scattered around the disk. Fragmentation also occurs as a result of adding data to a file. Fragmentation makes longer the time to access the magnetic disk drive since the seek time and rotary latency increase.
In order to clear up fragmentation in the magnetic disk device, the host apparatus performs a task called defragmentation. Defragmentation refers to a task which sequentially reallocates scattered file information to contiguous sectors or clusters. To perform defragmentation, the host apparatus must, for example, move data XYZ from cluster A to cluster B. In this case, the host apparatus sends a read command to read data XYZ into the memory of the host apparatus from cluster A and writes data XYZ to cluster B. Then, the host apparatus receives a write completion command from the magnetic disk drive and update the management table so as to change the storage location of data XYZ to cluster B from cluster A. This is because the magnetic disk drive typically performs nothing but to receive a read or write command with a sector LBA from the host apparatus and execute the command. Therefore, to move data stored in a sector on the magnetic disk, the host apparatus reads the data into its memory and then sends to the magnetic disk drive a write command with the destination sector LBA specified. After data is moved to another cluster in the magnetic disk device, the file management system of the host apparatus recognizes the destination cluster as the storage location of the data.
In Japanese Patent Laid-open No. 10-301721, a technique is disclosed which concerns how to reallocate sectors in order to solve the problem that the transfer rate would deteriorate as a consequence of using alternate sectors prepared for defective sectors. User data are rewritten in an alternate region and the allocation of LBAs to sectors is renewed by skipping the primary and secondary defective sectors. Then, the user data including those recorded in a save region are recorded in the sectors which are given new LBAs. Since the sectors given new LBAs do not use any sectors in the save region, the data access time can be reduced. In this case, the file management system of the host apparatus does not recognize that the storage locations of the data are changed. Changing the LBAs of sectors and moving data are implemented only by changing a reallocation defect map in the magnetic device.